# 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

# 返回 s 所有可能的分割方案。

# 示例:

# 输入: "aab"
# 输出:
# [
# ["aa","b"],
# ["a","a","b"]
# ]

# 来源：力扣（LeetCode）
# 链接：https://leetcode-cn.com/problems/palindrome-partitioning
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处
from typing import List


class Solution:
    def __init__(self):
        self.res = []

    def find(self, s, l):
        if s == "":
            self.res.append(l)
            return

        for i in range(len(s)):
            if s[:i+1] and self.valid(s[:i+1]):
                self.find(s[i+1:], l + [s[:i+1]])

    def partition(self, s: str) -> List[List[str]]:
        self.find(s, [])
        return self.res

    def valid(self, string):
        if not string:
            return False
        return string == string[::-1]


print(Solution().partition("12321"))
